School

Схема на Хорнер - метод за бързо делене на произволен полином на полином от вида $(x-p)$

Нека $A(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$ и $B(x)=x-p$. Тогава полиномът $A$ може да представи по следния начин, където $R$ е константа, защото степента му е по-малка от степента на делителя $B(x)$:

$$A(x)=(x-p)Q(x)+R$$

Коефициентите $q_1,q_2,...,q_{n-1}$ на $Q(x)$ и остатъкът $R$ се намират като се извършат действията в следната таблица

Теорема на Безу - остатъкът $R$ при делението на полинома $A(x)$ с $B(x)=x-p$ е равен на стойността на полинома $A(x)$ за $x=p$, т.е. $R=A(p)$.

а) доказателство

$$A(p)=(p-p)Q(p)+R=R$$

Преобразуване на полиноми

а) от нормален вид във вид на степени на $x-p$

$$\begin{array}{rl}A(x)& =a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0\\ & =a_n^{\prime }(x-p{)}^n+a_{n-1}^{\prime }(x-p{)}^{n-1}+\cdots +a_1^{\prime }(x-p)+a_0^{\prime }\end{array}$$

• търсят се коефициентите $a_n^{\prime },a_{n-1}^{\prime },\cdots ,a_1^{\prime },a_0^{\prime }$
• изваждаме $(x-p)$ пред скоби

$$A(x)=(x-p)[a_n^{\prime }(x-p{)}^{n-1}+a_{n-1}^{\prime }(x-p{)}^{n-2}+\cdots +a_1^{\prime }]+a_0^{\prime }$$

• следователно $a_0^{\prime }$ е остатъкът при делението на $A(x)$ на $(x-p)$
• по същия начин, чрез повторено изваждане на $(x-p)$ пред скоби се намират и останалите коефициенти - общо $n+1$ деления
• това може да се направи бързо чрез схемата на Хорнер

б) от вид на степени на $(x-p)$ във нормален вид

$$\begin{array}{rl}A(x-p)& =a_n^{\prime }(x-p{)}^n+a_{n-1}^{\prime }(x-p{)}^{n-1}+\cdots +a_1^{\prime }(x-p)+a_0^{\prime }\\ & =a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0\end{array}$$

• търсят се коефициентите $a_n,a_{n-1},\cdots ,a_0$
• полагаме $t=x-p⟹x=t+p$
• следователно \begin{align}A(x-p) = A(t) &= a_n(t+p)^n + a_{n-1}(t+p)^{n-1} + \cdots + a_1(t+p) + a_0 \&= a_n't^n + a_{n-1}'t^{n-1} + \cdots + a_1't + a_0'\end{align}
• задачата се свежда до представянето на полинома $A(t)$ по степени на $t+p$